// https://leetcode.cn/problems/same-tree/
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool flag = true;
    bool isSameTree(TreeNode* p, TreeNode* q) {
        compare(p, q);
        return flag;
    }

    void compare(TreeNode *n1, TreeNode *n2){
        if(n1 == nullptr && n2 != nullptr || n1 != nullptr && n2 ==nullptr){
            flag = false;
            return;
        }
        if (n1 != nullptr && n2 != nullptr) {
            if(n1->val != n2->val){
                flag = false;
                return;
            }
            compare(n1->left, n2->left);
            compare(n1->right, n2->right);
        }
    }

    TreeNode *init() {
        TreeNode *n1 = new TreeNode(1);
        TreeNode *n2 = new TreeNode(2);
        TreeNode *n3 = new TreeNode(3);
        TreeNode *n4 = new TreeNode(4);
        TreeNode *n5 = new TreeNode(5);
        n3->left = n4;
        n4->left = n1;
        n3->right = n2;
        n2->right = n5;

        return n3;
    }
};

int main() {
    Solution so;
    TreeNode * h1 = so.init();
    TreeNode * h2 = so.init();
    so.isSameTree(h1, h2);
    so.show(head);
    cout << endl;
    return 0;
}